COMMENT ⊗   VALID 00002 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	\documentstyle[11pt]{article}
C00010 ENDMK
C⊗;
\documentstyle[11pt]{article}
\textwidth 6.5in
\textheight 8.8in
\oddsidemargin 0pt
\evensidemargin 0pt
\topmargin 0pt
\headsep 0pt

\begin{document}
\title{Sentinels}
\author{Robert W. Floyd}
\maketitle
(Assumes knowledge of {\tt WHILE})

I want a program to read a long list of numbers and add them, printing the
sum at the end. I could use the definite iteration (``{\tt FOR}''), preceding the
list with a count of how many data there are.

\begin{verbatim}
INPUT:   3     2.1    3.5     4.2

PROGRAM: (Declarations and such)
         READ (N)
         SUM:= 0;
         FOR I:= 1 TO N DO
                BEGIN
                READ (X)
                SUM:= SUM + X
                END
         END.

OUTPUT:  9.8
\end{verbatim}
There are two disadvantages:

\begin{enumerate}
\item    The user must spend time counting the data, whether there are 
         three or three thousand.

\item    If the user counts wrongly, the program may omit some data at
         the end, without any obvious symptom of error, or may try to read
         more data than there are, resulting in an end-of-file error.
\end{enumerate}
Instead, I follow the data with a special value I know will not occur among
the data. If the data are the amounts of the checks I have written this
month, 999999 will do fine:
\begin{verbatim}
INPUT:  2.1     3.5     4.2     999999.0
\end{verbatim}
The 999999.0 has no quantitative meaning; it is called a {\em sentinel}.

I want an algorithm which initializes {\tt SUM} to zero. It then repeatedly
reads, and as long as it reads a non-zero value, increases {\tt SUM} by that
value. For the input above, the sequence of computational operations
should be:
\begin{verbatim}
SUM:= 0
READ (X)   (X=2.1)
TEST X < BIG: TRUE
SUM:= SUM+X   (SUM=2.1)
READ (X)   (X=3.5)
TEST X < BIG: TRUE
SUM:= SUM+X   (SUM=5.6)
READ (X)   (X=4.2)
TEST X < BIG: TRUE
SUM:= SUM+X   (SUM=9.8)
READ (X)   (X=999999.0)
TEST X < BIG: FALSE
WRITE(SUM)    (Print 9.8)
\end{verbatim}
where {\tt BIG} is a constant like 900000.0.

Some of these operations must be repeated as many times as needed; the {\tt READ},
the test, and the addition to {\tt SUM} must therefore be inside an iteration.
Other operations, like initializing {\tt SUM} to zero and printing its final value,
are done once and must not be iterated. Since the indefinite iteration
(``{\tt WHILE}'') starts with a test, the pattern of each repetition must be:
\begin{verbatim}
(TEST)
SUM:= SUM+X
READ (X)
\end{verbatim}
followed by a final test which finds that ${\tt X}\geq {\tt BIG}$.

Suppose there are n data to be added, followed by one sentinel to mark the
end. There must be $n+1$ reads to bring in all these numbers, including the
sentinel. Each number must be tested, so there are $n+1$ tests. Only n of the data
need be added to {\tt SUM}, though.
\newline Since the form
\begin{verbatim}
        WHILE condition DO S  
\end{verbatim}
makes the test once more than it executes {\tt S}, the relation between the number
of tests and the number of additions is right, but one extra {\tt READ} is needed.
Furthermore, the first test whether ${\tt X}\geq {\tt BIG}$ only makes sense if 
{\tt X} has already been read. I must have a {\tt READ(X)} before the 
iteration, as well as one inside.  Putting these requirements together, 
I get the iteration
\begin{verbatim}
WHILE X<BIG DO
        BEGIN
        SUM:= SUM+X;
        READ (X)
        END
\end{verbatim}
preceded by
\begin{verbatim}
SUM:= 0
READ (X)
\end{verbatim}
and followed by
\begin{verbatim}
WRITE(SUM).
\end{verbatim}
The whole program is:
\begin{verbatim}
PROGRAM P(INPUT);
CONST BIG = 900000.0;
VAR SUM, X: REAL;
BEGIN
SUM:= 0;
READ (X);
WHILE X<BIG DO
        BEGIN
        SUM:= SUM+X;
        READ (X)
        END;
WRITE(SUM)
END.
\end{verbatim}
The above program exemplifies a common pattern, where the iteration obtains
a set of data values and the last one is treated specially as a sentinel.
The first data value must be obtained before the iteration is entered.
The body of the iteration processes one data value, then obtains the next
one. Because some steps are done $n$ times, and some $n+1$ times, such iterations
are called n-and-a-halfs. There are other ways to write them, but most have
pitfalls. A potential error in this kind of problem is to forget that the
number of data 
might be zero (suppose the program above is part of a larger program for
balancing my bank account, I've made deposits but written no checks this
month, and I want to bring my account balance up to date).  
If there are no data, the program above reads the sentinel into {\tt X} before 
entering the iteration. Then, because {\tt X} is 999999.0, the iteration is 
instantly terminated, 
{\tt SUM} correctly remains zero, and is printed. Many otherwise 
plausible solutions fail when there are no data at all.
\end{document}